The introduction of high bandwidth services and the development of optical transmission equipment capable of carrying multi-giga bytes of digitized data in seconds have brought about major new considerations in the design of telecommunications networks. While the former demands networks with vastly larger transmission capacities, the latter creates the need for network designs that are considerably more fault-tolerant than the networks in operation today.
The traditional design of facilities networks was principally based on schemes that took advantage of the multiplexing hierarchy to improve the utilization of high bandwidth facilities through hubbing arrangements. Multi-giga byte systems, however, bring the reliability issue to the fore. The failure of one such system or channel at the hub node or link level could result in loss of a considerable percentage of the total demand provisioned in the network, with the concomitant loss of revenues. (See, for instance, the articles in THE NEW YORK TIMES on various outages due to fiber breaks or CO burn outs. "Much Of East Coast Phone Service Is Disrupted By Jersey Cable Break", NEW YORK TIMES, Nov. 19, 1988, p.1, and "AT&T Acting To Thwart New Mass Disruption", NEW YORK TIMES, Nov. 20, 1988, p.37.)
Among the many proposed schemes to make networks survivable, the concept of self-healing ring may be the most promising. In this scheme, network nodes and links that support high bandwidths are connected together on physically diverse closed paths (rings) in such a way that all the traffic that is served by the ring can be recovered in the event of a node or link failure (excluding the traffic originating or terminating at a failed node, which cannot be recovered). The technology that makes this possible is called the Synchronous Optical Network (SONET) standard for optical transmission and the underlying architecture is referred to as a SONET ring. (See G. R. Ritchie, "SONET Lays the Roadbed for Broadband Networks", NETWORKING MANAGEMENT (1990) for more details about the SONET standard).
At present, the SONET transmission standards allow for three distinct survivable ring designs: the (two-fiber) uni-directional ring and the two-fiber and four-fiber bi-directional rings. Depending on the amount of traffic demanded between locations on the ring, the distance between adjacent ring locations, the cost of SONET equipment and the cost of fiber facilities, one of these designs will be most economical.
Among the many new challenging problems in network design that SONET gives rise to, the most immediate is that of determination of the minimum cost survivable ring components. Since the cost of a ring is directly related to its bandwidth/bit rate, this problem is identical to that of minimizing the bandwidth ("load") on each survivable ring sub-component.
In order to select the appropriate ring design for a given situation, one must first determine a candidate topology for the ring over the set of network nodes. Then a potential design must be evaluated based upon how the traffic would be routed. The capacity of the ring is then set to accommodate this traffic and any additional traffic that would be created because of a link or node failure. Once the required capacity for each design is calculated, the associated costs for equipment and facilities can be compared.
The capacity of a SONET ring must be at least as large as the load experienced by any one of the links, should a failure occur. For uni-directional designs, this means that the ring capacity is at least as large as the sum of all of the point-to-point demands that are carried on the ring. For bi-directional ring designs, on the other hand, the required capacity is dependent on how each of the demands is routed on the ring.
Prior art solutions to this problem are inefficient since they require the evaluation of 2.sup.n demand routings, where n demands are present. This strategy is, in the best of situations, time consuming, and in even average situations, impossible, given large values of n.